package _mst;

import _object.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 面试题 04.06. 后继者
 */
public class T0406 {
    private Queue<TreeNode> queue;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        queue = new LinkedList<>();
        dfs(root);
        while (!queue.isEmpty()) {
            if (queue.poll() == p) break;
        }
        return queue.isEmpty() ? null : queue.poll();
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left);
        queue.offer(node);
        dfs(node.right);
    }
}
